题目 | 难度 |
---|---|
1. 两数之和 | 简单 |
15. 三数之和 | 中等 |
414. 第三大的数 | 简单 |
605. 种花问题 | 简单 |
350. 两个数组的交集 II | 简单 |
14. 最长公共前缀 | 简单 |
# 1. 两数之和
给定一个整数数组
nums
和一个整数目标值target
,请你在该数组中找出 和为目标值target
的那 两个 整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1:
输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
2
3
示例 2:
输入:nums = [3,2,4], target = 6
输出:[1,2]
2
思路:
这题考察的不是双层 for 循环暴力解题,而是转换思路,用 map,减少使用一层 for 循环,降低时间复杂度解题:
- 创建一个
map
for
循环遍历nums
数组- 用
target
减nums[i]
,计算哪个数能跟当前数相加得到target
- 检查
map
中有没有这个数,- 如果有,返回结果
- 如果没有,则把
nums[i]
当作key
,当作value
放入map
中(map.has()
方法检查map
中是否有对应的key
值)
- 用
给你一个整数数组 nums ,判断是否存在三元组
[nums[i], nums[j], nums[k]]
满足i != j
、i != k
且j != k
,同时还满足nums[i] + nums[j] + nums[k] == 0
。请你返回所有和为
0
且不重复的三元组。注意:答案中不可以包含重复的三元组。
示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。
2
3
4
5
6
7
8
示例 2:
输入:nums = [0,1,1]
输出:[]
解释:唯一可能的三元组和不为 0 。
2
3
示例 3:
输入:nums = [0,0,0]
输出:[[0,0,0]]
解释:唯一可能的三元组和为 0 。
2
3
思路:
- 给数组排序
- 遍历数组,从
0
遍历到length-2
- 如果当前这个数等于前一个数,则跳过这个数
- 如果数字不相同,则设置
start =i+1
,end =length-1
,查看i
,start
和end
三数之和大于还是小于0
- 如果小于
0
,start++
- 如果大于
0
,end--
- 如果等于
0
,把这三个数加入结果中,返回结果,并设置start =i+1
,end =length-1
,继续循环
- 如果小于
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function (nums) {
const result = [];
nums.sort(function (a, b) {
return a - b;
});
for (let i = 0; i < nums.length - 2; i++) {
if (i === 0 || nums[i] !== nums[i - 1]) {
let start = i + 1,
end = nums.length - 1;
while (start < end) {
if (nums[i] + nums[start] + nums[end] === 0) {
result.push([nums[i], nums[start], nums[end]]);
start++;
end--;
//防止重复项
while (start < end && nums[start] === nums[start - 1]) {
start++;
}
//防止重复项
while (start < end && nums[end] === nums[end + 1]) {
end--;
}
} else if (nums[i] + nums[start] + nums[end] < 0) {
start++;
} else {
end--;
}
}
}
}
return result;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# 3.第三大的数
给你一个非空数组,返回此数组中 第三大的数 。如果不存在,则返回数组中最大的数。
示例 1:
输入:[3, 2, 1]
输出:1
解释:第三大的数是 1 。
2
3
示例 2:
输入:[1, 2]
输出:2
解释:第三大的数不存在, 所以返回最大的数 2 。
2
3
示例 3:
输入:[2, 2, 3, 1]
输出:1
解释:注意,要求返回第三大的数,是指在所有不同数字中排第三大的数。
此例中存在两个值为 2 的数,它们都排第二。在所有不同数字中排第三大的数为 1
2
3
4
var thirdMax = function (nums) {
// 数组去重
let newArr = Array.from(new Set(nums))
//排序
newArr.sort((a, b) => a - b)
if (newArr.length < 3) { return newArr[newArr.length - 1] }
return newArr[newArr.length - 3]
};
2
3
4
5
6
7
8
Array.from()
Array.from()
方法是ES6新增方法,用于将两类对象转为真正的数组:
- 类似数组的对象(array-like object)
- 和可遍历(iterable)的对象(包括 ES6 新增的数据结构 Set 和 Map)。
let arrayLike = {
0: 'tom',
1: '65',
2: '男',
3: ['jane','john','Mary'],
'length': 4
}
let arr = Array.from(arrayLike)
console.log(arr) // ['tom','65','男',['jane','john','Mary']]
//将上面代码中length属性去掉,答案会是一个长度为0的空数组。
2
3
4
5
6
7
8
9
10
# 4. 种花问题
假设有一个很长的花坛,一部分地块种植了花,另一部分却没有。可是,花不能种植在相邻的地块上,它们会争夺水源,两者都会死去。
给你一个整数数组
flowerbed
表示花坛,由若干0
和1
组成,其中0
表示没种植花,1
表示种植了花。另有一个数n
,能否在不打破种植规则的情况下种入n
朵花?能则返回true
,不能则返回false
。
示例 1:
输入:flowerbed = [1,0,0,0,1], n = 1
输出:true
2
示例 2:
输入:flowerbed = [1,0,0,0,1], n = 2
输出:false
2
思路:
var canPlaceFlowers = function (flowerbed, n) {
// 能种几朵花
let count = 0
// 解除边界限制
flowerbed.push(0)
flowerbed.unshift(0)
for (let i = 0; i < flowerbed.length - 1; i++) {
// 相邻3个空位可以种一朵花
if (flowerbed[i] === 0 && flowerbed[i + 1] === 0 && flowerbed[i - 1] === 0) {
count++
flowerbed[i] = 1 // 补花
}
}
return count >= n
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 5. 两个数组的交集 II
给你两个整数数组
nums1
和nums2
,请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数,应与元素在两个数组中都出现的次数一致(如果出现次数不一致,则考虑取较小值)。可以不考虑输出结果的顺序。
示例 1:
输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2,2]
2
示例 2:
输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[4,9]
2
思路:
此题可以看成是一道传统的映射题(map映射),因为我们需找出两个数组的交集元素,同时应与两个数组中出现的次数一致。这样就导致了我们需要知道每个值出现的次数,所以映射关系就成了<元素,出现次数>。
const intersect = (nums1, nums2) => {
const map = {};
const res = [];
if (nums1.length < nums2.length) {
[nums1, nums2] = [nums2, nums1]
}
//map[key]并返回对应的值
for (num1 of nums1) {//nums1中各个元素的频次
if (map[num1]) {
map[num1]++;
} else {
map[num1] = 1;
}
}
for (num2 of nums2) { //遍历nums2
const val = map[num2];
if (val > 0) { //在nums1中
res.push(num2); //加入res数组
map[num2]--; //匹配掉一个,就减一个
}
}
return res;
};
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 6. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串
""
。说明:所有输入只包含小写字母
a-z
示例 1:
输入:strs = ["flower","flow","flight"]
输出:"fl"
2
示例 2:
输入:strs = ["dog","racecar","car"]
输出:""
解释:输入不存在公共前缀。
2
3
标签:链表
- 当字符串数组长度为 0 时则公共前缀为空,直接返回
- 令最长公共前缀 ans 的值为第一个字符串,进行初始化
- 遍历后面的字符串,依次将其与 ans 进行比较,两两找出公共前缀,最终结果即为最长公共前缀
- 如果查找过程中出现了 ans 为空的情况,则公共前缀不存在直接返回
- 时间复杂度:O(s)O(s),s 为所有字符串的长度之和